package org.eerbaar.parser.cky;

import org.eerbaar.parser.core.Grammar;
import org.eerbaar.parser.core.Parser;
import org.eerbaar.parser.core.def.NonTerminal;
import org.eerbaar.parser.core.def.NonTerminalProduction;
import org.eerbaar.parser.core.def.Production;
import org.eerbaar.parser.core.def.Symbol;
import org.eerbaar.parser.core.def.TerminalProduction;
import org.eerbaar.parser.core.def.impl.DefaultTerminalProduction;
import org.eerbaar.parser.core.exe.HasChildren;
import org.eerbaar.parser.core.exe.SymbolInstance;
import org.eerbaar.parser.core.exe.impl.DefaultSymbolInstance;

/**
 * A Cooke-Kasami-Younger (CKY) parser for a context-free grammar (
 * {@link Grammar}). The grammar must be in Chomsky normal form, i.e. restricted
 * to non-terminal productions ({@link NonTerminalProduction}) on the form A
 * -&gt; B C, and terminal productions ({@link parsing.TerminalProduction}) on
 * the form A -&gt; b. However, any context-free grammar can be converted into
 * an equivalent CNF grammar.
 * 
 * <pre>
 * let the input be a string S consisting of n characters: a1 ... an.
 * let the grammar contain r nonterminal symbols R1 ... Rr.
 * This grammar contains the subset Rs which is the set of start symbols.
 * let P[n,n,r] be an array of booleans. Initialize all elements of P to false.
 * for each i = 1 to n
 *   for each unit production Rj -> ai
 *     set P[i,i,j] = true
 * for each i = 2 to n -- Length of span
 *   for each j = 1 to n-i+1 -- Start of span
 *     for each k = 1 to i-1 -- Partition of span
 *       for each production RA -> RB RC
 *         if P[j,k,B] and P[j+k,i-k,C] then set P[j,i,A] = true
 * if any of P[1,n,x] is true (x is iterated over the set s, where s are all the indices for Rs) then
 *   S is member of language
 * else
 *   S is not member of language
 * </pre>
 * 
 * @author Eva Forsbom
 * @author evafo@stp.lingfil.uu.se
 * @version 0.11
 * @version 2005-10-24
 */
public class CKYParser
    implements Parser {

    private final Grammar grammar;
    private final NonTerminal[] nonTerminals;
    private SymbolInstance topSymbol;
    private boolean debug = false;
    private boolean success = false;
    private CKYParserData data;

    /**
     * Creates a Cooke-Kasami-Younger parser for the given grammar.
     * 
     * @param grammar
     *            A grammar in Chomsky normal form.
     */
    public CKYParser(Grammar grammar) {
        this.grammar = grammar;
        this.nonTerminals = grammar.getNonTerminals();
    }

    private boolean contains(TerminalProduction[] ts, TerminalProduction test) {
        boolean success = false;
        for (TerminalProduction terminalProduction : ts) {
            if (terminalProduction.equals(test)) {
                success = true;
            }
        }
        return success;
    }

    @Override
    public boolean getResult() {
        return this.success;
    }

    @Override
    public SymbolInstance next() {
        return this.data.next();
    }

    @Override
    public boolean parse(NonTerminal in_category, SymbolInstance[] in_sequence) {

        // create recogniser matrix
        data = new CKYParserData(in_sequence);

        // initialise strings of length 1 (terminals)
        TerminalProduction[] ts = grammar.getTerminalProductions();

        for (int j = 1; j <= in_sequence.length; j++) {
            for (int k = 0; k < nonTerminals.length; k++) {

                TerminalProduction test = new DefaultTerminalProduction(
                        nonTerminals[k], in_sequence[j - 1]);

                if (contains(ts, test)) {
                    // m.setR(1, j, k, true);
                    Symbol symbol = in_sequence[j - 1];

                    Symbol non = nonTerminals[k];
                    SymbolInstance w = new DefaultSymbolInstance(non, symbol,
                            j - 1, j);

                    data.getLevels().getLevel(1).getSymbolArray(symbol)
                            .setSymbol(w);
                    if (debug) {
                        // System.out.print(m);
                    }
                }
            }
        }

        // compute strings of length n > 1
        NonTerminalProduction[] nts = grammar.getNonTerminalProductions();

        // string of length > 1
        for (int i = 2; i <= in_sequence.length; i++) {
            // at start position j=1 <= n-i+1
            for (int j = 1; j <= in_sequence.length - i + 1; j++) {
                // previous string of lengths t=1 <= t=i-1
                for (int t = 1; t <= i - 1; t++) {
                    // for each production Ra -> Rb Rc
                    // if P[j,t,B] and P[j+t,i-t,C] then set P[j,i,A] = true
                    for (Production prod : nts) {

                        Level level1 = data.getLevels().getLevel(t);
                        SymbolArray s1 = level1.getSymbolArray(j);
                        Level level2 = data.getLevels().getLevel(i - t);
                        SymbolArray s2 = level2.getSymbolArray(j + t);
                        Symbol ks1 = prod.getRHS()[0];
                        Symbol ks2 = prod.getRHS()[1];

                        if (s1.hasSymbol(ks1) && s2.hasSymbol(ks2)) {
                            Level currentLevel = data.getLevels().getLevel(i);
                            SymbolInstance child1 = s1.getSymbol(ks1);
                            SymbolInstance child2 = s2.getSymbol(ks2);
                            HasChildren w = new DefaultSymbolInstance(
                                    prod.getLHS(), child1, child2);
                            currentLevel.getSymbolArray(j).setSymbol(
                                    (SymbolInstance) w);
                        }

                        if (debug) {
                            // System.out.print(m);
                        }
                    }
                }
            }
        }

        if (debug) {
            System.out.println(data);
        }
        Level level = data.getLevels().getLevel(in_sequence.length);
        SymbolArray array = level.getSymbolArray(1);
        success = array.hasSymbol(in_category);
        if (success) {
            topSymbol = array.getSymbol(in_category);
            System.out.println(new SymbolPrinter().print(topSymbol));
        }
        return success;
    }

    @Override
    public void remove(SymbolInstance symbol) {
        data.remove(symbol);
    }

    @Override
    public void setDebug(boolean debug) {
        this.debug = debug;
    }

}